package day20210625;

import treenode.SimpleTreeNode;

/**
 * 解决方案
 * 111. 二叉树的最小深度
 *
 * @author lizy
 * @date 2021/06/25
 */
public class Solution3 {
    public static void main(String[] args) {
        Solution3 solution = new Solution3();
        SimpleTreeNode simpleTreeNode = new SimpleTreeNode();
        simpleTreeNode.val = 1;
        simpleTreeNode.right = new SimpleTreeNode(2);
        simpleTreeNode.right.left = new SimpleTreeNode(3);
        simpleTreeNode.right.right = new SimpleTreeNode(3);
        System.out.println(solution.minDepth(simpleTreeNode));
    }


    private int minDepth(SimpleTreeNode root) {
        if (root == null) {
            return 0;
        }
        // 计算左子树的深度
        int left = minDepth(root.left);
        // 计算右子树的深度
        int right = minDepth(root.right);
        // 如果左子树或右子树的深度不为 0，即存在一个子树，那么当前子树的最小深度就是该子树的深度+1
        // 如果左子树和右子树的深度都不为 0，即左右子树都存在，那么当前子树的最小深度就是它们较小值+1
        return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
    }
}
